package org.codetranslators.common.optimization;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Vector;
import java.util.Stack;

import org.codetranslators.common.ControlFlowGraph;
import org.codetranslators.common.ControlFlowNode;
import org.codetranslators.common.DominatorTree;
import org.codetranslators.common.DominatorTreeNode;
import org.codetranslators.common.Edge;
import org.codetranslators.common.Node;
import org.codetranslators.common.Temp;
import org.codetranslators.common.Utilities;
import org.codetranslators.compiler.intermrep.AssemblyInstruction;
import org.codetranslators.compiler.intermrep.CJump;
import org.codetranslators.compiler.intermrep.Operation;

public abstract class OptimizationStrategy {
	public abstract ControlFlowGraph getOptimizedFlowGraph(ControlFlowGraph controlFlowGraph);
}

class SSA extends OptimizationStrategy {
	
	private ControlFlowGraph controlFlowGraph;
	private HashMap useDefChain;
	private HashMap defUseChain;
	
	Vector<AssemblyInstruction> transformedQuadruples;   // The list of transformed quadruples
	
	public ControlFlowGraph getOptimizedFlowGraph(ControlFlowGraph controlFlowGraph) {
		
		this.controlFlowGraph = controlFlowGraph;
		useDefChain = new HashMap<String, AssemblyInstruction>();
		defUseChain = new HashMap<Temp, HashSet<Temp>>();
		
		// Initialize the list of transformed quadruples from the original list of quadruples
		transformedQuadruples = new Vector<AssemblyInstruction>();
		Vector<AssemblyInstruction> originalQuadruples = controlFlowGraph.getQuadruples();
		int numQuads = originalQuadruples.size();
		for(int i = 0; i < numQuads; i++){
			transformedQuadruples.addElement(originalQuadruples.elementAt(i));
		}
		
		// Create the dominance tree
		DominatorCalculationContext dominatorCalculationContext = 
			new DominatorCalculationContext(controlFlowGraph, controlFlowGraph.getStartNode());
		dominatorCalculationContext.setLengauerTarjan();
		
		DominatorTree dominatorTree = dominatorCalculationContext.getDominatorTree();

		DominatorTreeNode dominatorTreeNode = dominatorTree.getDominatorTreeRoot();
		
		System.out.println("DOMINATOR TREE: ");
		dominatorTreeNode.display();
		
		sortDominatorTree(dominatorTree, dominatorTreeNode);
		
		System.out.println("SORTED DOMINATOR TREE: ");
		dominatorTreeNode.display();
		
		// Calculate the dominance frontiers
		//HashMap dominanceFrontiers = getDominanceFrontiers(controlFlowGraph, dominatorTree);
		HashMap dominanceFrontiers = Utilities.getDominanceFrontiers(controlFlowGraph, dominatorTree);
		
		displayDominanceFrontiers(dominanceFrontiers);
		
		// Insert the phi functions
		insertPhiFunctions(dominanceFrontiers);
		
		// Rename the variables
		renameVariables(dominatorTree);
		
		System.out.println("FINISHED RENAMING; SSA FORM IS READY ...........");
		
		// Now the control flow graph is in SSA form; perform the optimizations
		performOptimizationsOnSSA();
		
		return this.controlFlowGraph;
	}
	
	private void insertPhiFunctions(HashMap dominanceFrontiers) {
		
		HashMap variableVsNodesNeedingPhiFunctions = new HashMap();
		
		HashMap variableVsNodeDefined = new HashMap(); // A map of variable versus the nodes in which
													   // it is defined
		
		// Populate the above map (variableVsNodeDefined)
		for(int i = 0; i < controlFlowGraph.getNumNodes(); i++) {
			ControlFlowNode controlFlowNode = (ControlFlowNode) controlFlowGraph.getNode(i);
			
			HashSet definitions = controlFlowNode.getDefinitions();
			Iterator iterator = definitions.iterator();
			while(iterator.hasNext()) {
				Temp temp = (Temp) iterator.next();
				addNodeToDefSite(temp, controlFlowNode, variableVsNodeDefined);
			}
		}
		
		//printTempVsNodesDefined(variableVsNodeDefined);
		
		// Get the list of "global" variables - these are variables that are used in several blocks;
		// that is, they are either defined or used in more than one block. Use only these variables
		// for the worklist
		HashMap newVariableVsNodeDefined = new HashMap();
		HashSet globals = getGlobalVariables();
		Iterator iterGlobals = globals.iterator();
		while(iterGlobals.hasNext()){
			Temp temp = (Temp)iterGlobals.next();
			HashSet workList = (HashSet)variableVsNodeDefined.get(temp);
			newVariableVsNodeDefined.put(temp, workList);
		}
		
		// Using a worklist, for each node containing the definition of a variable, 
		// insert phi functions in dominance frontiers of that node
		Vector variables = controlFlowGraph.getVariables();
		for(int i = 0; i < variables.size(); i++){
			Temp temp = (Temp) variables.elementAt(i);
			
			HashSet workList = (HashSet)newVariableVsNodeDefined.get(temp);  // The worklist of nodes in which 
																		  // the temp is defined
			
			if(workList == null) continue;
			
			while(!workList.isEmpty()) {
				Iterator iterator = workList.iterator();
				ControlFlowNode defNode = (ControlFlowNode)iterator.next();
				workList.remove(defNode);
				
				// Insert phi functions for each node in the dominance frontier of defNode
				HashSet dominanceFrontierOfNode = (HashSet)dominanceFrontiers.get(defNode);
				if(dominanceFrontierOfNode == null) continue;
				Iterator dfIter = dominanceFrontierOfNode.iterator();
				while(dfIter.hasNext()){
					ControlFlowNode frontierNode = (ControlFlowNode) dfIter.next();
					
					// If this is the last (exit) node in the graph, ignore it
					if(frontierNode == controlFlowGraph.getEndNode()) continue;
					
					HashSet nodesWithPhiFuncsForVariable = (HashSet)
							variableVsNodesNeedingPhiFunctions.get(temp);
					if(nodesWithPhiFuncsForVariable == null) nodesWithPhiFuncsForVariable = new HashSet();
					if(!nodesWithPhiFuncsForVariable.contains(frontierNode)) {
						int numPreds = frontierNode.getNumIncomingEdges();
						SSAPhiFunction phiFunction = new SSAPhiFunction(temp, numPreds); 
						Vector<AssemblyInstruction>  instrsInNode = frontierNode.getInstructions();
						instrsInNode.add(1, phiFunction);  // Add the phi function after the label
						
						// Update the list of transformed quadruples
						Vector<AssemblyInstruction> newInstrs = new Vector<AssemblyInstruction>();
						newInstrs.add(phiFunction);   // The only new instruction
						int index = getIndexForInstructionInTransformedListing(instrsInNode.elementAt(0));
						transformedQuadruples.addAll(index+1, newInstrs);
										
						// Add the frontier node to the list of nodes with phi functions for the variable
						nodesWithPhiFuncsForVariable.add(frontierNode);
						variableVsNodesNeedingPhiFunctions.put(temp, nodesWithPhiFuncsForVariable);
						
						// Add the frontier node to the work-list (if it already exists, it will not be added)
						workList.add(frontierNode);
					}
				}
			}
		}
	}
	
	/*
	 * Returns the index for a given quadruple in the list of transformed quadruples
	 */
	private int getIndexForInstructionInTransformedListing(AssemblyInstruction insertAfterIns){
		int index = 0;
		int numTransQuads = transformedQuadruples.size();
		for(index = 0; index < numTransQuads; index++){
			AssemblyInstruction instrFound = (AssemblyInstruction) transformedQuadruples.elementAt(index);
			if(instrFound == insertAfterIns) return index;
		}
		return index;
	}
	
	
	
	private void addNodeToDefSite(Temp temp, ControlFlowNode controlFlowNode,
			HashMap variableVsNodeDefined ) {
		
		HashSet nodesDefinedIn = (HashSet) variableVsNodeDefined.get(temp);
		if(nodesDefinedIn == null) nodesDefinedIn = new HashSet();
		nodesDefinedIn.add(controlFlowNode);
		variableVsNodeDefined.put(temp, nodesDefinedIn);
	}
	
	private void displayDominanceFrontiers(HashMap dominanceFrontiers){
		// Display the dominance frontiers
		System.out.println("DOMINANCE FRONTIERS: ");
		int numGraphNodes = controlFlowGraph.getNumNodes();
		for(int j = 0; j < numGraphNodes; j++){
			Node node = (Node) controlFlowGraph.getNode(j);
			System.out.print("Node " + node.getName() + ": ");
			HashSet members = (HashSet) dominanceFrontiers.get(node);
			if(members != null){
				Iterator iter = members.iterator();
				while(iter.hasNext()){
					Node mem = (Node) iter.next();
					System.out.print(mem.getName() + ", ");
				}
			}
			System.out.println("");
		}
	}
	
	private HashSet getGlobalVariables(){
		HashSet globals = new HashSet();
		int numNodes = controlFlowGraph.getNumNodes();
		for(int i = 0; i < numNodes; i++){
			ControlFlowNode cfNode = (ControlFlowNode)controlFlowGraph.getNode(i);
			//System.out.println("### Adding to globals from block - " + cfNode.getName());
			Vector quads = cfNode.getInstructions();
			HashSet varsKilledInNode = new HashSet();
			int numIns = quads.size();
			for(int j = 0; j < numIns; j++){
				AssemblyInstruction ins = (AssemblyInstruction) quads.elementAt(j);
				Vector defs = ins.getDestList();
				Vector srcs = ins.getSrcList();
				if(srcs != null){
					for(int a = 0; a < srcs.size(); a++){
						Temp srcTemp = (Temp) srcs.elementAt(a);
						if(!varsKilledInNode.contains(srcTemp)){
							//System.out.println(srcTemp.toString());
							globals.add(srcTemp);
						}
					}
				}
				if(defs != null){
					for(int a = 0; a < defs.size(); a++){
						Temp defTemp = (Temp) defs.elementAt(a);
						varsKilledInNode.add(defTemp);
					}
				}
			}
		}
		
		return globals;
	}
	
	private void renameVariables(DominatorTree dominatorTree){
		
		/*Node strtNode = controlFlowGraph.getStartNode();
		Node wantedNode = null;
		int numNodes = controlFlowGraph.getNumNodes();
		for(int i = 0; i < numNodes; i++){
			Node nd = controlFlowGraph.getNode(i);
			if(nd.getName().equals("L5")){
				wantedNode = nd;
				break;
			}
		}
		*/
		
		HashMap variableVsCount = new HashMap();
		HashMap variableVsStack = new HashMap();
		
		// For each variable count, initialize the variable definition count 
		// and a stack to maintain the current number
		Vector variables = controlFlowGraph.getVariables();
		for(int i = 0; i < variables.size(); i++){
			Temp temp = (Temp) variables.elementAt(i);
			Integer countInt = new Integer(0);
			variableVsCount.put(temp, countInt);
			Stack stack = new Stack();
			stack.push(new Integer(0));
			variableVsStack.put(temp, stack);
				
		}
		
		HashMap<String, AssemblyInstruction> tempNameVsDefinitionInstruction = new HashMap<String, AssemblyInstruction>();
		
		
		rename(controlFlowGraph.getStartNode(), variableVsCount, variableVsStack, dominatorTree,
				tempNameVsDefinitionInstruction);
	}
	
	private void rename(ControlFlowNode controlFlowNode, HashMap variableVsCount, HashMap variableVsStack,
			            DominatorTree dominatorTree, HashMap tempNameVsDefinitionInstruction){
		Vector quads = controlFlowNode.getInstructions();
		
		Vector definitionsInNode = new Vector();  // This list has all definitions defined in the 
												  // control flow node passed
		
		for(int i = 0; i < quads.size(); i++) {
			AssemblyInstruction quadruple = (AssemblyInstruction) quads.elementAt(i);
			Vector srcList = quadruple.getSrcList();
			Vector destList = quadruple.getDestList();
			Vector renamedSrcList = null;
			Vector renamedDestList = null;
			if(quadruple.getType() != AssemblyInstruction.SSA_PHI_FUNCTION){
				// Not a phi function; rename the source variables.
				if(srcList != null){
					renamedSrcList = new Vector();
					for(int a = 0; a < srcList.size(); a++){
						Temp srcTemp = (Temp) srcList.elementAt(a);
						if(srcTemp.isPhysicalRegister()) {
							renamedSrcList.add(srcTemp);
							continue;
						}
						
						Stack stack = (Stack) variableVsStack.get(srcTemp);
						Integer countInt = (Integer) stack.lastElement();
						int count = countInt.intValue();
						
						SSATemp newTemp = new SSATemp(srcTemp, count);
						renamedSrcList.addElement(newTemp);	
						
						// Populate the new source temp against the site of it's definition - this is the 
						// use-def chain; for an SSA form, there will be only one definition
						AssemblyInstruction defSiteInstruction = 
							(AssemblyInstruction)tempNameVsDefinitionInstruction.get(newTemp.toString());
						if(defSiteInstruction != null)
							useDefChain.put(newTemp.toString(), defSiteInstruction);
						
						// Get the corresponding temporary defined in the quadruple and add to it's  use
						Temp definedTemp = (Temp)defSiteInstruction.getDestList().elementAt(0);  // Assume only variable is defined
						HashSet<Temp> usages = (HashSet<Temp> )defUseChain.get(definedTemp);
						if(usages == null){
							usages = new HashSet<Temp>(); // No uses found so far; add this source as an usage
							
						}
					}
				}
			}
			else{
				// This is an SSA phi function; populate the use-def chain
				for(int a = 0; a < srcList.size(); a++){
					Temp srcTemp = (Temp)srcList.elementAt(a);
					AssemblyInstruction defSiteInstruction = 
						(AssemblyInstruction)tempNameVsDefinitionInstruction.get(srcTemp.toString());
					if(defSiteInstruction != null)	
						useDefChain.put(srcTemp.toString(), defSiteInstruction);
					
				}
			}
				
			// Rename the destination variables
			if(destList != null) {
				renamedDestList = new Vector();
				for(int a = 0; a < destList.size(); a++){
					Temp newTemp = null;
					Temp destTemp = (Temp) destList.elementAt(a);
					if(destTemp.isPhysicalRegister())
						newTemp = destTemp;            // This is a physical register; do not rename
					else
						newTemp = newName(destTemp, variableVsCount, variableVsStack);
					renamedDestList.addElement(newTemp);
					definitionsInNode.addElement(destTemp);
				}
			}
			
			// Now that we have created new temporaries for the source and destination, create a new quadruple
			quadruple = createNewQuadruple(quadruple, renamedDestList, renamedSrcList);
			
			// If there are destination variables, populate the map of the variable definition against 
			// the new quadruple - useful in determing def-use chains
			if(destList != null){
				for(int a = 0; a < renamedDestList.size(); a++){
					Temp destTemp = (Temp)renamedDestList.elementAt(a);
					String destTempName = destTemp.toString();
					tempNameVsDefinitionInstruction.put(destTempName, quadruple);
				}
			}
			
			// Set the new quadruple in the control flow node
			quads.set(i, quadruple);
		}
			
		// For each successor in the flow graph for this control flow node, if there are phi functions
		// in some successor, replace the parameter values of phi function 
		updatePhiFunctionParams(variableVsStack, controlFlowNode);
		
		// Recursively call rename on this node's children in the dominator tree
		Vector childTreeNodes = dominatorTree.getChildNodesForGraphNode(controlFlowNode);
		for(int a = 0; a < childTreeNodes.size(); a++){
			ControlFlowNode childCFGNode = (ControlFlowNode) childTreeNodes.elementAt(a);
			rename(childCFGNode, variableVsCount, variableVsStack, dominatorTree, tempNameVsDefinitionInstruction);
		}
	
		// Pop the the new definitions in this node to expose count in the  stack
		for(int i = 0; i < definitionsInNode.size(); i++){
			Temp tmp = (Temp) definitionsInNode.elementAt(i);
			Stack stack = (Stack)variableVsStack.get(tmp);
			stack.pop();
		}
	}
	
	private AssemblyInstruction createNewQuadruple(AssemblyInstruction quadruple, 
									Vector renamedDestList, Vector renamedSrcList){
		AssemblyInstruction newQuad  = null;
		int type = quadruple.getType();
		if(type == AssemblyInstruction.CALL || type == AssemblyInstruction.JUMP 
				|| type == AssemblyInstruction.LABEL){
			newQuad = quadruple;  // No change
		}
		else if(type == AssemblyInstruction.CJUMP){
			CJump cJump = (CJump) quadruple;
			newQuad = new CJump(renamedSrcList, cJump.getTrueLabel() , cJump.getFalseLabel(), 
					cJump.getRelOp(), cJump.getImmediateValue());
		}
		else if(type == AssemblyInstruction.INSTRUCTION){
			Operation opr = (Operation)quadruple;
			newQuad = new Operation(renamedDestList, renamedSrcList, opr.getOperationCode(),
									opr.getImmediateValue(), opr.getLabel());
		}
		else {
			// Must be a phi function
			SSAPhiFunction phiFunc = (SSAPhiFunction)quadruple;
			Temp destTemp = (Temp)renamedDestList.elementAt(0);  // The SSA form will have only one destination
																 // variable
			newQuad = new SSAPhiFunction(destTemp, phiFunc.getSrcList(), phiFunc.getCurrentParamNumberToBeRenamed());
		}
		return newQuad;
	}
	
	/*
	 * Creates a new Temp of type SSATemp - this encapsulates <old_name>_n<num>
	 */
	private Temp newName(Temp temp, HashMap variableVsCount, HashMap variableVsStack){
		Integer countInt = (Integer)variableVsCount.get(temp);
		int currCount = countInt.intValue();
		currCount++;
		
		variableVsCount.put(temp, new Integer(currCount));
		Stack stack = (Stack)variableVsStack.get(temp);
		stack.push(new Integer(currCount));
		variableVsStack.put(temp, stack);
		
		String newTempName = temp.toString() + "_n" + currCount;
		Temp newTemp = new Temp(temp.getNum(), newTempName);
		return newTemp;
	}
	
	/*
	 * Updates the parameter names of the phi functions in successors of a control flow node.
	 */
	public void updatePhiFunctionParams(HashMap variableVsStack, ControlFlowNode controlFlowNode){
		Vector cfNodeSuccessors = controlFlowNode.getSuccessors();
		if(cfNodeSuccessors == null) return;   // Does not have successors
		
		for(int i = 0; i < cfNodeSuccessors.size(); i++){
			ControlFlowNode successor = (ControlFlowNode) cfNodeSuccessors.elementAt(i);
			
			// For this successor, find the index at which the control flow node passed to this function 
			// is a predecessor. This will determine the index at which the phi function parameter has
			// to be renamed
			
			Vector predecessorsOfSuccessor = successor.getPredecessors();
			int paramNum = 0;
			for(int a = 0; a < predecessorsOfSuccessor.size(); a++){
				Node predOfSuccessor = (Node)predecessorsOfSuccessor.elementAt(a);
				if(predOfSuccessor == controlFlowNode){
					paramNum = a;
					break;
				}
			}
			
			
			Vector quadsOfSuccessor = successor.getInstructions();
			for(int j = 0; j < quadsOfSuccessor.size(); j++){
				AssemblyInstruction quadruple = (AssemblyInstruction) quadsOfSuccessor.elementAt(j);
				if(quadruple.getType() == AssemblyInstruction.SSA_PHI_FUNCTION){
					// This is a phi function; replace the appropriate parameter with the new name
					SSAPhiFunction phiFunc = (SSAPhiFunction)quadruple;
					phiFunc.updateParamName(variableVsStack, paramNum);
					quadsOfSuccessor.set(j, phiFunc);
				}
			}
		}
	}
	
	/**
	 * This method will sort out the children of each node in the dominator tree passed to it,
	 * so that the new order reflects the order of children in the control flow graph. This will help in 
	 * maintaining a consistent ordering while renaming variables
	 * @param dominatorTree
	 */
	
	private void sortDominatorTree(DominatorTree dominatorTree, DominatorTreeNode dominatorTreeNode){
		
		Vector childrenOfDominatorTreeNode = dominatorTreeNode.getChildren();
		
		Node graphNode = dominatorTreeNode.getGraphNode();
		Vector childrenOfGraphNode = graphNode.getSuccessors();
	
		Vector orderedDominatorChildren = new Vector();
		
		for(int j = 0; j < childrenOfGraphNode.size(); j++){
			Node nd = (Node) childrenOfGraphNode.elementAt(j);
			DominatorTreeNode dmTreeNode = dominatorTree.getDominatorTreeNode(nd);
			if(childrenOfDominatorTreeNode.contains(dmTreeNode))
			{
				orderedDominatorChildren.addElement(dmTreeNode);
			}
		}
		
		// Now loop through the list of children of the the dominator tree node and 
		// add the missing children at the end
		Vector remainingNodes = new Vector();
		for(int i = 0; i < childrenOfDominatorTreeNode.size();i++){
			DominatorTreeNode dmTreeNode = (DominatorTreeNode)childrenOfDominatorTreeNode.elementAt(i);
			if(!orderedDominatorChildren.contains(dmTreeNode))
				remainingNodes.addElement(dmTreeNode);
		}
		
		for(int k = 0; k < remainingNodes.size(); k++){
			DominatorTreeNode dmTreeNode = (DominatorTreeNode)remainingNodes.elementAt(k);
			orderedDominatorChildren.addElement(dmTreeNode);
		}
		
		// Add the ordered dominator children to the dominator tree node
		dominatorTreeNode.setChildren(orderedDominatorChildren);
		
		// Sort each of the children
		for(int m = 0; m < orderedDominatorChildren.size(); m++)
		{
			DominatorTreeNode dmTreeNode = (DominatorTreeNode)orderedDominatorChildren.elementAt(m);
			sortDominatorTree(dominatorTree,dmTreeNode);
		}
	}
	
	private void performOptimizationsOnSSA()
	{
		// At this point, the control flow graph is in SSA form; perform the optimizations
		
		// ***** Test print the use-def chain
		System.out.println("USE-DEF CHAIN:");
		Set set = useDefChain.entrySet();
		Iterator iterTest = set.iterator();
		while(iterTest.hasNext()){
			Map.Entry entr = (Map.Entry) iterTest.next();
			String tmp = (String)entr.getKey();
			AssemblyInstruction instr = (AssemblyInstruction) entr.getValue();
			
			if(instr != null)
				System.out.println("Temp = " + tmp + ", Def-site instruction = " + instr.getAssemCode(false));
			else
				System.out.println("Unable to find a def site for temp" + tmp.toString());
			
		}
		
		
		deadCodeElimination(); // Dead code elimination
		otherOptimizations();
	}
	
	private void deadCodeElimination()
	{
		// First Create the inverse flow graph from the given control flow graph which is in SSA form
		int numCFGNodes = controlFlowGraph.getNumNodes();
		
		ControlFlowGraph reverseCFG = new ControlFlowGraph();
		
		ControlFlowNode endNode = controlFlowGraph.getEndNode();
		updateReverseCFG(endNode, reverseCFG);
		
		// Now we have the SSA in the reverse form, create the dominator tree from it
		DominatorCalculationContext dominatorCalculationContext = 
			new DominatorCalculationContext(reverseCFG, reverseCFG.getStartNode());
		dominatorCalculationContext.setLengauerTarjan();
		DominatorTree dominatorTree = dominatorCalculationContext.getDominatorTree();
		
		// Get the dominance frontiers - this will determine the reverse dominance frontier in the
		// original flow graph
		HashMap<ControlFlowNode, HashSet<ControlFlowNode>> reverseDominanceFrontiers =
			new HashMap<ControlFlowNode, HashSet<ControlFlowNode>>();
		HashMap dominanceFrontiers = Utilities.getDominanceFrontiers(reverseCFG, dominatorTree);
		Set entries = dominanceFrontiers.entrySet();
		Iterator iter = entries.iterator();
		while(iter.hasNext())
		{
			Map.Entry entry = (Map.Entry) iter.next();
			ControlFlowNode cfNode = (ControlFlowNode) entry.getKey();
			HashSet dfNodes = (HashSet)entry.getValue();
			ControlFlowNode cfNodeOriginalFlowGraph = controlFlowGraph.getNodeWithName(cfNode.getName());
			
			HashSet dfOriginal = new HashSet();
			Iterator dfIter = dfNodes.iterator();
			while(dfIter.hasNext()){
				ControlFlowNode dfMember = (ControlFlowNode) dfIter.next();
				ControlFlowNode cfNodeOriginalFlowGraphMember = 
					controlFlowGraph.getNodeWithName(dfMember.getName());
				dfOriginal.add(cfNodeOriginalFlowGraphMember);
			}
			
			reverseDominanceFrontiers.put(cfNodeOriginalFlowGraph, dfOriginal);
		}
		
		// Get all critical operations
		HashSet criticalOperations = getCriticalOperations();
		
		System.out.println("Num of initial critical operations found = " + criticalOperations.size());
		
		// Using the set of critical operations as a work-list, mark out other operations as critical
		// that are dependent on already marked ones
		HashSet<AssemblyInstruction> allCriticalOperations = new HashSet<AssemblyInstruction>();
		while(criticalOperations.size() > 0){
			// Remove the first instruction
			iter = criticalOperations.iterator();
			
			AssemblyInstruction instr = (AssemblyInstruction)iter.next();
			criticalOperations.remove(instr);
			allCriticalOperations.add(instr);   // Add to final list
			
			// Get the list of source variables; for each source, add the instruction that defines it;
			// to get the instruction that defines it, use the use-def chain. There will be only
			// one definition site since this is in SSA form
			Vector srcList = instr.getSrcList();
			
			if(srcList != null){
				for(int i = 0; i < srcList.size(); i++){
					Temp srcTemp = (Temp) srcList.elementAt(i);
					AssemblyInstruction defSite = (AssemblyInstruction)useDefChain.get(srcTemp.toString());
					if(defSite != null){
						if(!allCriticalOperations.contains(defSite))criticalOperations.add(defSite);
						System.out.println("ADDING USEFUL OPERATION: " + defSite.getAssemCode(false));
						allCriticalOperations.add(defSite);
					}
				}
			}
			
			
			// For the block in which the instruction is located, get the reverse dominance frontiers;
			// For each block in the frontier, get the last statement which could be a branch and mark it
			ControlFlowNode nodeOfInstruction = controlFlowGraph.getCFNodeForQuadruple(instr);
			HashSet<ControlFlowNode> reverseDF = reverseDominanceFrontiers.get(nodeOfInstruction);
			
			if(reverseDF != null){
				// The node has a set of reverse dominance frontiers; iterate through them
				// to identify the last statement (branch) in each of them
				Iterator dfIter = reverseDF.iterator();
				while(dfIter.hasNext()){
					ControlFlowNode dfMember = (ControlFlowNode) dfIter.next();
					Vector instrsInNode = dfMember.getInstructions();
					AssemblyInstruction lastInstr = (AssemblyInstruction)instrsInNode.lastElement();
					if(lastInstr.getType() == AssemblyInstruction.CJUMP){
						if(!allCriticalOperations.contains(lastInstr))criticalOperations.add(lastInstr);
						allCriticalOperations.add(lastInstr);
					}
				}
			}
		}
		
		// Remove the list of instructions from the flow graph now, by iterating through each control flow node.
		// Remove an instruction if it is in the not in the list of all critical operations AND it is neither
		// a jump nor a label. Also, if the instruction a branch and is not a critical operation, replace the 
		// branch with a jump to the nearest marked postdominator
		int numNodes = controlFlowGraph.getNumNodes();
		for(int a = 0; a < numNodes; a++ ){
			ControlFlowNode cfNode = (ControlFlowNode) controlFlowGraph.getNode(a);
			Vector instrsInNode = cfNode.getInstructions();
			for(int i = 0; i < instrsInNode.size(); i++){
				AssemblyInstruction instr = (AssemblyInstruction) instrsInNode.elementAt(i);
				if(!allCriticalOperations.contains(instr)){
					int type = instr.getType();
					if(type == AssemblyInstruction.CJUMP){
						// Replace the branch with a jump to the nearest marked postdominator
					}
					else if(!(type == AssemblyInstruction.LABEL || type == AssemblyInstruction.JUMP)){
						System.out.println("REMOVING INSTRUCTION: " + instr.getAssemCode(false));
						instrsInNode.remove(instr);
						i--;
					}
				}
			}
		}
	}
	
	/*
	 * This function populates the reverse control flow graph; it is called recursively for each node in the 
	 * original control flow graph. The first parameter, cfNode is a node in the original control flow graph.
	 */
	
	private void updateReverseCFG(ControlFlowNode cfNode, ControlFlowGraph reverseCFG){
		
		// If the corresponding control flow node does not already exist in the reverse flow graph, 
		// add it
		ControlFlowNode reversedNode = reverseCFG.getNodeWithName(cfNode.getName());
		if(reversedNode == null){
			// Node with same name does not exist; create a new control flow node
			// corresponding to the one in the original flow graph and add it 
			reversedNode = cfNode.createClone();
			reverseCFG.addNode(reversedNode);
			if(cfNode.getPredecessors().size() == 0)   
				reverseCFG.setEndNode(reversedNode);
			
			if(cfNode.getSuccessors().size() == 0)
				reverseCFG.setStartNode(reversedNode);
		}

		// Get the predecessors of the node passed and make them successors to the corresponding
		// node in the reverse flow graph
		Vector preds = cfNode.getPredecessors();
		int numPreds = preds.size();
		for(int i = 0; i < numPreds; i++){
			ControlFlowNode predecessorNode = (ControlFlowNode)preds.elementAt(i);
			String predecessorNodeName = predecessorNode.getName();
			
			// If a node with the same name exists in the reverse flow graph, do not
			// add it again
			ControlFlowNode reversedNodeOfPred = reverseCFG.getNodeWithName(predecessorNodeName);
			if(reversedNodeOfPred != null){
				Edge edge = new Edge(reversedNode, reversedNodeOfPred);
				reverseCFG.addDirectedEdge(edge, reversedNode, reversedNodeOfPred);
				continue;
			}
			
			reversedNodeOfPred = predecessorNode.createClone();
			reverseCFG.addNode(reversedNodeOfPred);
			
			Edge edge = new Edge(reversedNode, reversedNodeOfPred);
			reverseCFG.addDirectedEdge(edge, reversedNode, reversedNodeOfPred);

			updateReverseCFG(predecessorNode, reverseCFG);
			
		}
	}
	
	private HashSet<AssemblyInstruction> getCriticalOperations(){
		
		// Create a work-list of all critical operations - these include storing into memory,
		// function calls, phi-functions and jumps, Input/Output (not handled here) and 
		// operations whose destination variables are machine registers (for example - $ra, $v0, etc. 
		// for MIPS)
		HashSet<AssemblyInstruction> criticalOperations = new HashSet<AssemblyInstruction> ();
		
		int numNodes = controlFlowGraph.getNumNodes();
		for(int i = 0; i < numNodes; i++){
			ControlFlowNode node = (ControlFlowNode) controlFlowGraph.getNode(i);
			Vector instrsInNode = node.getInstructions();
			int numInstrs = instrsInNode.size();
			for(int j = 0; j < numInstrs; j++){
				AssemblyInstruction instr = (AssemblyInstruction)instrsInNode.elementAt(j);
				int instrType = instr.getType();
				
				// If this is a function call or a SSA Phi function mark it as critical 
				if(instrType == AssemblyInstruction.CALL || instrType ==  AssemblyInstruction.SSA_PHI_FUNCTION){
					// This is a useful instruction; mark it
					System.out.println("#### Adding as critical op: " + instr.toString());
					criticalOperations.add(instr);
				}
				else if(instrType == AssemblyInstruction.INSTRUCTION){
					// This is an instruction; if there is a store to a memory, mark it as critical
					Operation operation = (Operation) instr;
					int opType = operation.getType();
					if(opType == Operation.STORE_WORD_INTO_ADDRESS_AT_TEMP ||
							opType == Operation.STORE_WORD_INTO_CONST_ADDRESS)
					
					{
						System.out.println("#### Adding as critical op: " + instr.toString());
						criticalOperations.add(instr);
					}
				}
				
				// For this instruction, get a the list of destination variables; if one of them
				// represents a machine register, mark it as critical
				Vector destList = instr.getDestList();
				if(destList != null && destList.size() > 0){
					for(int k = 0; k < destList.size(); k++){
						Temp destTemp = (Temp)destList.elementAt(k);
						if(destTemp.isPhysicalRegister())
						{
							System.out.println("#### Adding as critical op: " + instr.toString());
							criticalOperations.add(instr);
						}
					}
				}
			}	
		}
		
		return criticalOperations;
	}
	
	/*
	 * This function uses a work-list algorithm for several other optimizations like copy propagation, 
	 * constant propagation, constant folding, constant conditions and eliminating unreachable code
	 */
	private void otherOptimizations(){
		/*
		// Create a worklist of all statements from the SSA program
		Vector<AssemblyInstruction> instrs = controlFlowGraph.getQuadruples();
		while(instrs.size() > 0){
			AssemblyInstruction insr = instrs.remove(0);
			if(insr.getType() == AssemblyInstruction.SSA_PHI_FUNCTION){
				
			}
			else{
				if(insr.getType() == AssemblyInstruction.
			}
		}
		
		*/
	}
}